package weaver.model;

import java.util.*;

/**
 * GameSolver is responsible for computing the shortest path in the Weaver game.
 * It uses a Breadth-First Search (BFS) algorithm to find the optimal sequence of valid moves
 * from the start word to the target word using a dictionary of valid words.
 */
public class GameSolver {
    private Set<String> dictionary;  // Set of valid words
    private String startWord;        // Starting word for the game
    private String targetWord;       // Target word for the game

    /**
     * Constructs a GameSolver with a given dictionary.
     *
     * @param dictionary the set of valid words to use in the search
     */
    public GameSolver(Set<String> dictionary) {
        this.dictionary = dictionary;
    }

    /**
     * Initializes the game with a start and target word.
     *
     * @param start  the starting word
     * @param target the target word
     */
    public void initializeGame(String start, String target) {
        assert start != null && target != null : "Start and target words must not be null";
        assert start.length() == target.length() : "Words must have the same length!";

        if (start.length() != target.length()) {
            throw new IllegalArgumentException("Words must have the same length!");
        }

        this.startWord = start.toUpperCase();
        this.targetWord = target.toUpperCase();
    }

    /**
     * Checks if one word is a valid one-step transformation from another.
     *
     * @param current the current word
     * @param next    the candidate next word
     * @return true if next is a valid step from current
     */
    public boolean isValidStep(String current, String next) {
        if (current.length() != next.length()) return false;
        if (!dictionary.contains(next.toLowerCase())) return false;

        int diffCount = 0;
        for (int i = 0; i < current.length(); i++) {
            if (current.charAt(i) != next.charAt(i)) diffCount++;
            if (diffCount > 1) return false; // More than one letter difference
        }
        return diffCount == 1; // Must differ by exactly one letter
    }

    /**
     * Finds the shortest path from start to target word using BFS.
     *
     * @return list of words representing the shortest path, or an empty list if no path found
     */
    public List<String> findShortestPath() {
        Queue<List<String>> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();

        // Start with the path containing only the start word
        queue.offer(Arrays.asList(startWord));
        visited.add(startWord);

        while (!queue.isEmpty()) {
            List<String> path = queue.poll();
            String current = path.get(path.size() - 1);

            // If we've reached the target, return the successful path
            if (current.equals(targetWord)) {
                return path;
            }

            // Explore valid neighbors (1-letter variations in the dictionary)
            for (String neighbor : getNeighbors(current)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    List<String> newPath = new ArrayList<>(path);
                    newPath.add(neighbor);
                    queue.offer(newPath);
                }
            }
        }

        // No valid path found
        return Collections.emptyList();
    }

    /**
     * Generates all valid neighbor words by changing one letter at a time.
     *
     * @param word the current word
     * @return list of valid 1-letter-different words found in the dictionary
     */
    private List<String> getNeighbors(String word) {
        List<String> neighbors = new ArrayList<>();
        char[] chars = word.toCharArray();

        // Try replacing each letter with every other alphabet letter
        for (int i = 0; i < word.length(); i++) {
            char original = chars[i];
            for (char c = 'A'; c <= 'Z'; c++) {
                if (c != original) {
                    chars[i] = c;
                    String newWord = new String(chars);
                    if (dictionary.contains(newWord.toLowerCase())) {
                        neighbors.add(newWord);
                    }
                }
            }
            chars[i] = original; // Restore the original character
        }

        return neighbors;
    }
}
